package me.zk.practice1.s;

import java.util.Arrays;

/**
 * @author zhangkai
 * @date 2023/8/11 09:31
 */
public class LSLCR101 {
    public static void main(String[] args) {
        canPartition(new int[]{1,5,11,5,4,4});
    }
    public static boolean canPartition(int[] nums) {
        if (nums.length==1) {
            return false;
        }
        int sum = 0;
        int max = 0;

        for (int num : nums) {
            sum+=num;
            max = Math.max(num,max);
        }
        if (sum%2!=0){
            return false;
        }

        int target = sum/2;

        if (max > target) {
            return false;
        }

        boolean[][] dp = new boolean[nums.length+1][target+1];
        dp[0][0] = true;
        // i 为选取的长度
        //j 为和
        for (int i = 1; i <= nums.length; i++) {

            for (int j = 0; j <= target; j++) {
                //如果目标值小于当前值，说明不能加，只能取i-1之前的和
                if (j < nums[i-1]) {
                    dp[i][j] = dp[i-1][j];

                } else {
                    dp[i][j] = dp[i-1][j]||dp[i-1][j-nums[i-1]];
                }

            }
        }
        for (int i = 0; i <= nums.length; i++) {
            for (int j = target; j <= target; j++) {
                System.out.println(dp[i][j]);
            }
        }

        return dp[nums.length][target];
    }
}
